package algorithm.swordoff;


import java.util.Stack;

/**
 * 栈的压入、弹出序列
 *
 * 初始化： 辅助栈 stack ，弹出序列的索引 i ；
 * 遍历压栈序列： 各元素记为 num ；
 * 元素 num 入栈；
 * 循环出栈：若 stack 的栈顶元素 == 弹出序列元素 popped[i] ，则执行出栈与 i++ ；
 * 返回值： 若 stack 为空，则此弹出序列合法。
 *
 */


public class SQ31 {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int popIndex = 0;

        for (int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);
            while (!stack.isEmpty() && stack.peek() == popped[popIndex]) {
                stack.pop();
                popIndex++;  // 注意这个++不能写在while条件里,因为需要满足while条件之后才能++
            }
        }

        return stack.isEmpty();
    }

    public static void main(String[] args) {
        int[] a = {1,2,3,4,5};
        int[] b = {4,5,3,2,1};
        SQ31 sq31 = new SQ31();
        System.out.println(sq31.validateStackSequences(a, b));
    }
}
